1. Field of the Invention
The present invention relates to a system and method for assigning protocols for reuse of frequencies and codes in a wireless communication system utilizing spread spectrum technology. More particularly, the present invention relates to a system and method for maximizing channel utilization by efficiently allocating codes and frequencies based on estimated relative interference between subscriber units in a wireless communications network, such as an ad-hoc wireless communications network.
2. Description of the Related Art
Wireless communications networks, such as mobile wireless telephone networks, have become increasingly prevalent over the past decade. These wireless communications networks are commonly referred to as “cellular networks”, because the network infrastructure is arranged to divide the service area into a plurality of regions called “cells”.
Specifically, a terrestrial cellular network includes a plurality of interconnected base stations that are distributed geographically at designated locations throughout the service area. Each base station includes one or more transceivers that are capable of transmitting and receiving electromagnetic signals, such as radio frequency (RF) communications signals, to and from user terminals, such as wireless telephones, located in its coverage area. The communications signals include, for example, voice data that has been modulated according to a desired modulation technique and transmitted as data packets or frames. As can be appreciated by one skilled in the art, the transceiver and user terminals transmit and receive the data frames in multiplexed format, such as time-division multiple access (TDMA) format, code-division multiple access (CDMA) format, or frequency-division multiple access (FDMA) format, which enables a single transceiver at the base station to communicate simultaneously with several user terminals in its coverage area.
In addition, in a cellular wireless system, the base stations typically communicate with the user terminals over channels. The channel resources are assigned in order to limit interference between units and thus, minimize collisions between signals. The word “collision” will hereafter refer to the presence of two code/frequency combinations in the same geographical area that renders communication between units using such combinations ineffective, thus indicating that a better code/frequency combination should have been selected instead. In a Global System for Mobile Communications (GSM) network, for instance, frequencies are assigned to specific cell towers, allowing for a large-scale reuse pattern to take place. In CDMA/IS-95, spreading codes are dynamically assigned by the cell tower to neighboring units.
In general, in networks employing handheld multimedia terminals (HMT) as discussed below, conventional practice in performing collision avoidance was to simply verify whether a channel was used or not, which is also referred to as “carrier sensed/collision avoidance”. To overcome problems when collision could not be avoided, a different spreading code was chosen using the address of the desired receiving unit. Unfortunately, this code-planning technique only mitigated interference from other units, without taking advantage of the intrinsic properties of spreading codes.
FIG. 1 is a conceptual diagram illustrating a first network configuration in which channel utilization is determined based on a technique which will be hereafter referred to as “frequency collision threshold”. Each unit (displayed as a darkened circle within a second circle) includes a transceiver that is associated with a code/frequency pair. The number “ab” associated with each transceiver corresponds to the code/frequency pair assigned to each transceiver, in which “a” is the frequency (1 through 3) and “b” is the code (1 through 7). A 0 indicates that none (either frequency and/or code) is available. In certain cases, the interference will be such that no transmission will be possible without critically affecting other transmissions. In this event, the unit will elect not to transmit.
In a traditional carrier sense multiple access/collision avoidance (CSMA/CA) system, each unit is able to determine if a frequency channel is available. A “frequency collision threshold” method is designed to prevent units from reusing the same frequency channel at the same time when the amount of interference created would prevent successful communication from occurring. The threshold used in such a method would be selected in such a way that interference can still be mitigated by the use of different spreading codes. The advantage over a standard CSMA/CA system therefore resides in a greater channel utilization, since frequency channel resources are used more frequently as the frequency collision threshold is lowered.
As can be appreciated by one skilled in the art, common pathologies for the “frequency collision threshold” technique include code/frequency-reuse collisions. That is, as indicated in the circled area C1, there are four scheduled transmission using the “32” code/frequency pair. Also, another pathology is extensive frequency collisions, as indicated in the circled area C2, where code/frequency pairs “23”, “22” and “26” are inadequately located one next to another. To prevent such undesirable situations from occurring, one could increase the threshold. However, the outcome would be a dramatic reduction in network capacity as more units become unable to transmit for lack of available frequency channels. FIG. 2 therefore illustrates a second network configuration in which channel utilization is determined based on another technique which will hereafter be referred to as “code/frequency collision threshold”. The numbering and other terminology shown in FIG. 2 uses the same convention as that shown in FIG. 1 as discussed above.
The code/frequency collision threshold technique is similar to the “frequency collision threshold” technique demonstrated in FIG. 1, because it also probes the channel to prevent frequency collisions from occurring, yet also performs the same analysis for code collisions. Since codes do not usually provide sufficient processing gain to compensate for a lack of frequency separation, the threshold used to avoid code collisions is significantly higher than the one used to avoid frequency collisions. Thus, units using the same code/frequency pair are likely to be geographically further apart from one another. This phenomenon is illustrated in FIG. 2 with the triangles highlighting code/frequency pair “27”, squares highlighting the code/frequency pair “13”, and hexagons highlighting the code/frequency pair “31”.
However, other pathologies remain unresolved. For example, frequency reuse is far from optimized as indicated in circled area C3 in FIG. 2 (i.e., frequency 2 could be advantageously used in area C3). Accordingly, as can be appreciated from the above examples, a threshold approach cannot resolve these issues because it does not make judicious decisions; it only prevents catastrophic situations from occurring.
Other known techniques are also available for allocating channels. For example, one technique is described in a document by Arvind R. Raghavan entitled “An Unslotted Multichannel Channel-Access Protocol For Distributed Direct Sequence Networks”, Mobile Networks and Applications, Vol. 5, pp. 49–56 (2000), the contents of which is herein incorporated by reference. Specifically, this document describes a fully-connected system in which transceivers can transmit or receive on one frequency channel at a time. Transceivers monitor each frequency channel to ensure that they are appropriately used. Since each transceiver is given only one code, there is no possibility of “code-collision”. However, the question arises in a non-fully connected system as to what criterion may be used to prioritize the use of specific code/frequency pairs.
Other techniques for allocating channels in a communications network are also described in U.S. Pat. No. 6,229,796 to Dent, and in U.S. Pat. No. 6,128,500 to Rhaghavan et al., the entire contents of both being incorporated herein by reference. The Dent patent describes a method to allocate code, frequency and time slots in an optimal way for cellular systems. However, this method is entirely static and therefore makes assumptions about the geometry of the infrastructure which is not compatible with a self-forming ad hoc network. The Rhaghavan et al. patent provides an adaptive method to increase capacity in a cellular system, but it only modifies cell boundaries based on a measure of interference. It is not implementable in a self-forming network where there are no fixed base stations.
That is, in recent years, a type of mobile communications network known as an “ad-hoc” network has been developed for use by the military. In this type of network, each user terminal (hereinafter “mobile node”) is capable of operating as a base station or router for the other mobile nodes, thus eliminating the need for a fixed infrastructure of base stations. Accordingly, data packets being sent from a source mobile node to a destination mobile node are typically routed through a number of intermediate mobile nodes before reaching the destination mobile node. Details of an ad-hoc network are set forth in U.S. Pat. No. 5,943,322 to Mayor, the entire content of which is incorporated herein by reference.
More sophisticated ad-hoc networks are also being developed which, in addition to enabling mobile nodes to communicate with each other as in a conventional ad-hoc network, further enable the mobile nodes to access a fixed network and thus communicate with other types of user terminals, such as those on the public switched telephone network (PSTN) and on other networks such as the Internet. Details of these types of ad-hoc networks are described in U.S. patent application Ser. No. 09/897,790 entitled “Ad Hoc Peer-to-Peer Mobile Radio Access System Interfaced to the PSTN and Cellular Networks”, filed on Jun. 29, 2001, in U.S. patent application Ser. No. 09/815,157 entitled “Time Division Protocol for an Ad-Hoc, Peer-to-Peer Radio Network Having Coordinating Channel Access to Shared Parallel Data Channels with Separate Reservation Channel”, filed on Mar. 22, 2001, and in U.S. patent application Ser. No. 09/815,164 entitled “Prioritized-Routing for an Ad-Hoc, Peer-to-Peer, Mobile Radio Access System”, filed on Mar. 22, 2001, the entire content of each of said patent applications being incorporated herein by reference.
As with conventional wireless networks discussed above, it can be necessary to allocate frequency and code channels to the nodes via which the nodes communicate with each other. It is also therefore necessary for these channels to be allocated in such a manner as to limit interference between neighboring nodes while also avoiding collision between signals transmitted by the nodes. Thus, a need exists to provide an improved systematic methodology for allocating channels in a communications network, in particular, a wireless ad-hoc communications network, which selects a code/frequency pair for communication between two nodes in the network in such a way that multiple access interference is minimized.